#include "Stack.h"
//栈实现
bool StackInit(Stack* st)
{
	if (NULL == st)   //也可以使用assert只不过assert太过于暴力直接终止程序 if判断返回是一种温和的方法返回false
		return false;
	st->arr = NULL;
	st->capacity = 0;
	st->top = 0;
	return true;
}
bool StackDestroy(Stack* st)
{
	if (NULL == st)
		return false;
	free(st->arr);
	st->arr = NULL; //不要忘记对free后的指针置空
	st->capacity = st->top = 0;
	return true;
}

bool StackPush(Stack* st, STDataType x)
{
	if (st->capacity <= st->top)
	{
		int newcapacity = 0 == st->capacity ? 5 : st->capacity * 2;
		int* tmp = realloc(st->arr, newcapacity);//realloc时候如果原空间小于要需要申请的空间长度，系统会自动释放原空间，重新开辟新的要申请的空间
		if (NULL == tmp)
		{
			perror("malloc");
			return false;
		}
		st->arr = tmp;
		newcapacity = newcapacity;
		st->arr[st->top++] = x;
	}
	return true;
}

bool StackPop(Stack* st)
{
	assert(st);
	if (0 == st->top)
		return false;
	--(st->top); //注意：删除栈中的数据并不是真正意义上的删除而是伪删除
	return true;
}

int StackSize(Stack* st)
{
	assert(st);
	return st->top;
}
bool StackEmpty(Stack* st)
{
	assert(st);
	return st->top == 0;
}

//最小栈
class MinStack {
private:
    stack<int> data_stack;
    stack<int> min_satck;
public:
    MinStack() {
        min_satck.push(INT_MAX);
    }
    
    void push(int val) {
        if(data_stack.empty() || val < min_satck.top())//if(val < min.top()) //如果||前面的条件成立，则就不用执行||后的表达式
        {
            min_satck.push(val);
        }
        else
        {
            min_satck.push(min_satck.top());
        }
        data_stack.push(val);
    }
    
    void pop() {
        data_stack.pop();
        min_satck.pop();
    }
    
    int top() {
        return data_stack.top();
    }
    
    int getMin() {
        return min_satck.top();
    }
};

//有效括号
bool isValid(string s) {
        //首先根据s.length()判断，如果s的长度是奇数则不为有效括号
        if(s.length() & 1)
            return false;
        stack<char> mystack;
        unordered_map<char,char> pairs = {
            {')','('},
            {'}','{'},
            {']','['}
        };
        for(const auto& ch:s)
        {
            if(mystack.empty() || pairs[ch] != mystack.top())
                mystack.push(ch);
            else if(pairs[ch] == mystack.top())
            {
                mystack.pop();
            }
        }
        // if(!mystack.empty())
        //     return false;
        // return true;
        return mystack.empty();


        string removeDuplicates(string s) {
        stack<char> mystack;
        int size = s.length();
        int cur = 0;
        int judge = 1;
        while(cur < size)
        {
            if(mystack.empty() || mystack.top() != s[cur])
            {
                mystack.push(s[cur]);
                cur++;
            }
            else if(mystack.top() == s[cur])
            {
                while(mystack.top() == s[cur])
                {
                    cur++;
                    judge++;
                }
                if(judge%2 == 0)
                mystack.pop();
                judge = 1;
            }
        }
        s.clear();
        while(!mystack.empty())
        {
            s.push_back(mystack.top());
            mystack.pop();
        }
        std::reverse(s.begin(),s.end());
        return s;
    }